
// [[ex06be]]
// DEBUG descr Lock-free queue.
class queue 
{
public: 
	struct node {
		node * volatile next_;
		int payload_; // the payload may be of any type
	};

	queue()
	{
		first_ = divider_ = last_ = new node;
	}

	~queue()
	{
		while (first_ != 0) { 
			node *tmp = first_;
			first_ = first_->next_;
			delete tmp;
		}
	}

	// called by the writer thread; may use n==0 to
	// just do the cleaning
	void push_back(node *n)
	{
		// first, free any nodes that became unused
		while (first_ != divider_) {
			node *tmp = first_;
			first_ = first_->next_;
			delete tmp;
		}

		// then add the new node
		if (n != 0) {
			n->next_ = 0;
			last_->next_ = n;
			last_ = n;
		}
	}


	// called by the reader thread
	// returns the new node but doesn't delete it!
	// (or returns NULL if the queue is empty)
	node *front() const
	{
		if (divider_ == last_)
			return 0;
		return divider_->next_;
	}

	// called by the reader thread marks the node
	// previously returned by front() as read
	void pop_front()
	{
		// if the payload is more complicated, it can be
		// freed here
		divider_ = divider_->next_;
	}

protected:
	// the head of the list, used only by the writer
	// thread
	node *first_; 
	node * volatile divider_; 
	node * volatile last_;
};
// END

